The present invention relates to an improvement in a pattern matching apparatus used for a character or voice recognition system.
Although the pattern matching system of the invention can be broadly applied to time sequence pattern matching, the following description of the invention will be focussed on speech pattern by way of example.
Usually, a speech pattern can be expressed as a time sequence pattern of features. Speech recognition, therefore, is performed by comparing this time sequence pattern with a reference pattern, i.e., through pattern matching.
For high-accuracy speech recognition, it is necessary to adopt a pattern matching method which has a high pattern fluctuation adjusting capacity. As to distortion caused by time expansion and compression, a pattern matching method called DP (Dynamic Programming) proposed in part by the inventor has been satisfactorily employed. Details of the DP matching method are described in detail in, for example, U.S. Pat. No. 3,816,722, and in a paper by HIROAKI SAKOE and SEIBI CHIBA entitled "Dynamic Programming Algorithm Optimization for Spoken Word Recognition", IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-26, NO. 1, FEBRUARY 1978, pp. 43-49.
Actually, however, speech patterns include various deformations in addition to time expansion and compression distortion. For instance, partial deformation of vowels are often found in continuously uttered speech. Examples of such deformations are: nasalization in which, for example, a term "neck" [nek]is pronounced as [nek]; unvoicing in which, for example, a term "six" [siks] is pronounced as [sik]; omission in which, for example, a term piston [pistn] is pronounced as [pistn]; and elongation of vowels. These deformations do not appear consistently, but occur in quite an unpredictable manner depending on the speed of pronunciation, and phoneme at the preceding or succeeding side of the vowel.
Previously, in order to cope with the deformations of pronounciation, it has been necessary to prepare a plurality of reference patterns corresponding to various possible deformations. Especially for an unlimited number of speakers, a great number of reference patterns should be prepared. Therefore, the reference pattern itself must be quite flexible, and the matching process for comparing the input pattern with the reference pattern must be highly efficient. These are necessary also from the viewpoint of reducing the capacity of the reference pattern memory.
A DP matching method which is capable of solving these problems and which copes with such deformation was proposed (U.S. patent application Ser. No. 631,692, now U.S. Pat. No. 4,670,850) by the inventors of the present invention. In this method, a reference pattern uses a parenthesis type branch-control operator for instructing the branching in the time sequence. The specification says that the portion surrounded by the branching-control operator can be controlled so that several choices or omissions can be made. This method consists of the following basic constitutional requirements, namely, a reference pattern supplying means for supplying a reference feature sequence pattern containing control operators for controlling branching and/or omission; an input pattern supplying means for supplying an input pattern of input feature sequence; a distance computing section for computing the distance between the feature of the input pattern and the reference feature sequence pattern; a work memory having addresses adapted to be selected in accordance with the time point in the reference feature sequence pattern, and adapted to store the cumulative distance; a recurrence formula computing section for executing a DP matching recurrence formula computation in accordance with a plurality of values read out of the work memory and the resulting cumulative distance; a stack for storing the control operator and the position at which the control operator appears; and a stack processing section having a stack control section which, when the control operator is detected, the PUSH/POP operation of the stack in accordance with the kind of the detected control operator, thereby to control the DP matching recurrence formula computation which is to be conducted in the recurrence formula computing section.
However, in this method, it is demanded that a parenthesis appears without contradiction, and, therefore, the range of deformation which can be described by the reference pattern is narrow. A simple example will now be shown. Assume that the following three ways of deformation are permitted in a part of the time sequence of features. ##EQU1##
Such deformation can be expressed as follows by the branching controller used in the above-described method. EQU . . . {a b c d/e f {t s/{gc/h }d}} (2)
wherein "{" and "}" means selecting any one of the time sequences enclosed therein and divided by "/" and can be used in accordance with the inserting form.
The automaton expression shown in FIG. 1 corresponds to the reference pattern of the formula (2). This automaton can be simplified. The automaton shown in FIG. 2 is simpler and of the same value. The automaton shown in FIG. 1 requires the 10-state, while the automaton shown in FIG. 2 is described in the 8-state. Namely, a conventional method, in which the branching is expressed by a parenthesis form, has a redundant form in some cases, and requires a large number of memories for storing reference patterns. Moreover, the amount of computation for processing the reference patterns is large.
In addition, the branching-control operator has a limitation that "}" appears after "{" does, so that a loop-included automaton cannot be expressed.